Appendix A, which is a part of the present disclosure, is a listing of software code for embodiments of components of this invention, which are described more completely below.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
This invention relates to fingerprint verification. More particularly, this invention relates to methods for combining fingerprint templates obtained from various portions of a finger into one fingerprint template representing the combined fingerprint.
Biometric identification is used to verify the identity of a person by digitally measuring selected features of some physical characteristic and comparing those measurements with those filed for the person in a reference database, or sometimes on a smart card carried by the person. Physical characteristics that are being used include fingerprints, voiceprints, the geometry of the hand, the pattern of blood vessels on the wrist and on the retina of the eye, the topography of the iris of the eye, facial patterns and the dynamics of writing a signature and typing on a keyboard.
The fingerprint is one of the most widely used physical characteristics in biometric identification. Fingerprints are utilized as the most reliable means to identify individuals because of two outstanding characteristics, namely that they remain unchanged all through life and differ from individual to individual. Fingerprints consist of raised friction ridges of skin separated by recessed valleys of skin. Fingerprint xe2x80x9cminutiaexe2x80x9d are conventionally defined as ridge endings or ridge bifurcations where a ridge splits into two ridges.
Since the matching of a fingerprint as an image can require large file capacity to store the measured and referenced features and complex computation to match measured features with reference features, fingerprint identification is carried out using the positional relationship of features or minutiae that are extracted from the fingerprint image. The minutiae representing a fingerprint image are digitized and stored in a digital memory, which may be a read-only memory, magnetic tape, or the like. A fingerprint digitized in this manner may be compared with reference fingerprints stored in the memory. For the comparison to work, the reference fingerprint and the measured fingerprint must be extracted, characterized, and digitized so that the fingerprint templates contain the same information and have the same format.
As fingerprint sensing gains momentum in application, manufacturers are gearing up for high volume production, deploying both silicon-based sensors as well as the traditional optical sensors. As the production volumes increase, these manufacturers will continue to cost-reduce their products to stay competitive. One way to reduce cost is to decrease the size of the sensor. However, as the sensors get smaller, the matching accuracy is correspondingly reduced because less data is available for comparison. Furthermore, the size of the fingerprint sensor is often limited by the size of the finger in order to obtain a full fingerprint.
Placing the user""s finger on the sensor in different positions and then pasting the images of the sensed portions of the finger together is one solution in reducing the size of a fingerprint sensor. The images taken from the various areas of the finger are typically aligned with a registration software and essentially xe2x80x9cgluedxe2x80x9d together.
FIG. 1A shows an image 10 having a partial fingerprint of a finger. FIG. 1B shows an image 12 having a partial fingerprint from the same finger but at a different position. As can be seen from FIGS. 1A and 1B, image 10 overlaps image 12. For example, image 10 shows the top portion of a fingerprint while image 12 shows the bottom portion of the same fingerprint and both images 10 and 12 show the middle portion of the fingerprint. FIG. 1C shows an image 14 having a combined fingerprint derived by gluing images 10 and 12 together using an image correlation algorithm, for example, as described by Dana H. Ballard and Christopher M. Brown in a book entitled xe2x80x9cComputer Visionxe2x80x9d (1982) on pages 65-71, hereby incorporated by reference.
In image correlation, a template is created from a particular feature which is in effect a subimage. A similarity measure is computed which reflects how well the image data of another image match the template for each possible template location. The point of maximal match is then selected as the location of the feature. The template-matching calculations may be visualized by imagining the template being shifted across the image to different offsets to locate where in the image the feature occurs. The two images can then be aligned and combined.
However, image alignment, especially for poorly imaged fingers resulting from, for example, dry fingers, is a difficult task and is computationally expensive. Furthermore, because the finger has a fluid surface, the surface of the finger stretches and varies under different conditions. Hence, the ridge definition is rarely exactly the same twice. This inherent difference causes the overlap regions to be different, producing an artifact effect when glued together. In other words, the overlap region appears to be formed by two different sources because the transition at the overlap regions is not smooth. Therefore, the image correlation algorithm must take these conditions into account during the match, thereby requiring additional computation. A further problem is rotation which must be taken into account because the various portions of fingerprint may be obtained with the finger in different orientations.
Therefore, what is needed is a method for combining various templates from various portions of a finger, the method being computationally inexpensive.
A method for combining two templates. A first template having a first minutia set and a second template having a second minutia set are provided. In one embodiment, each template comprises at least one data chunk which represents one minutia. Each minutia is characterized by a location, a minutia angle and a neighborhood. The location further includes an x-coordinate and a y-coordinate. The neighborhood includes a plurality of neighbors, each having a distance from the selected minutia and two related angles. In one embodiment, all the parameters are quantized to reduce the bits required to represent the distance and the related angles of a minutia, hence decreasing the memory requirement.
The first template is compared with the second template to obtain a matching minutia set. The templates are compared on a data chunk by data chunk basis and by comparing each characterization parameters of the data chunks. Comparing on a data chunk by data chunk basis allows a computer with low computational power to execute the template matching algorithm. If all characterization parameters match, the data chunks match. The matching minutia pair is stored as a part of a matching minutia set in a memory accessible by a computer.
Registration parameters are calculated from the matching minutia set. Each registration parameter is calculated by summing the difference of each minutia pair in the matching minutia set and dividing the sum by the number of minutia pairs in the matching minutia set. In one embodiment, the registration parameters are in reference to the first minutia set. In another embodiment, the registration parameters are in reference to the second minutia set.
All minutiae in the minutia set that is not the reference minutia set are translated to be on the same coordinate system as the reference minutia set. The translation is done by adding the registration parameters to the characterization parameters of the minutia set that is not the reference minutia set. The minutia set and the translated minutia set are then combined to construct a combined minutia set. In one embodiment, an overlap region is drawn for the first minutia set and the second minutia set. In one embodiment, the overlap region is the smallest possible rectangle enclosing all matching minutiae. The combined minutia set is then constructed from the matching minutiae in the first or the second template, minutiae in the first minutia set that are not in the matching minutia set, and minutiae in the second minutia set that are not in the matching minutia set. In another embodiment, minutiae in the overlap region but not part of the matching minutia set are discarded.
By combining two templates from two images taken from a finger at different positions, a combined template representing the larger, combined image is obtained. This combined template can then be used in fingerprint matching. Hence, the size of the sensor can be decreased while retaining matching accuracy at a reduced cost.